(1) Field of the Invention
The present invention relates to a technology of performing memory access using the VIPT (Virtual Indexed Physical Tagged) architecture.
(2) Description of the Related Art
In order to make access to a direct map cache, the VIPT architecture has currently been employed. In the VIPT architecture, an access is made to a cache line of the cache memory based on a virtual index of a virtual address, and tag information (information indicating a physical page of the main memory, where data of the cache line was stored that is, information agreeing with a physical tag of the physical page) of the accessed cache line is read from the tag array. Address translation is performed on high-order bits of the virtual address to thereby obtain the physical tag of the physical address. Then, a cache hit or miss is determined by comparing the tag information read out from the tag array with the physical tag obtained by the address translation.
In the case where the size of the cache memory is larger than the physical page of the main memory, a so-called cache aliasing issue occurs. The following explains this cache aliasing issue.
FIG. 10 is used to explain cache lines, in a direct map cache memory, into which physical blocks are mapped. Assume that the size of the cache memory corresponds to two physical pages.
In this case, for example, it is cache lines line 1-1 and line 2-1 of the cache memory that into which physical blocks of physical pages page 1 to page m in line blk 1 of the main memory in FIG. 10 are possibly to be mapped. Similarly, it is cache lines line 1-n and line 2-n that into which physical blocks of physical pages page 1 to page m in line blk n are possibly to be mapped.
Among multiple cache lines into which a physical block is possibly to be mapped, cache lines that potentially have a cache aliasing relationship with one of the multiple cache lines are all the multiple cache lines except for this one cache line. For instance, a cache line that potentially has a cache aliasing relationship with the cache line line 1-1 is the cache line line 2-1, and a cache line that potentially has a cache aliasing relationship with the cache line line 2-1 is the cache line line 1-1.
FIG. 11 is used to explain the VIPT architecture. Assume that: the size of one physical page is 4 Kbytes; the size of the cache memory is 8 Kbytes; both the size of one cache line and the size of one physical block in the physical page are 16 bytes each; and one virtual address is 32 bits.
The size of the cache memory corresponds to two physical pages, and therefore, one physical address PA corresponds to two virtual addresses VA and VA′, for example.
Since the size of one cache line is 16 bytes, the offset for identifying a word in the cache line is 4 bits in the 3rd to 0th bits. Since the size of the cache memory is 8 Kbytes and the size of one cache line is 16 bytes, virtual indexes VI and VI′ for identifying cache lines in the cache memory are 9 bits in the 12th to 4th bits.
A virtual tag of 20 bits in the 31st to 12th bits of the virtual addresses VA and VA′ is converted into 20 bits of the physical address PA, located in the 31st to 12th bits. Within the physical address PA, 19 bits in the 31st to 13th bits form a physical tag TAG for identifying a physical page of the main memory. Note that the 12th bit of the physical address PA takes the same value for the virtual addresses VA and VA′.
For example, in the case where the virtual address VA is input, the physical tag TAG is compared with tag information stored in the tag array of a cache line corresponding to the virtual index VI of the virtual address VA. When they agree with each other, it is determined as a cache hit; when they do not agree, it is determined as a cache miss.
FIG. 12 is used to explain a cache aliasing issue.
Assume, for example, that a first process makes memory access using the virtual address VA while a second process makes memory access using the virtual address VA′. In this case, as shown in (a) of FIG. 12, in the tag array, tag information indicating a physical page P0 which includes the physical address PA corresponding to the virtual addresses VA and VA′ is stored in entries of cache lines corresponding to the virtual indexes VI and VI′ of the cache memory. In the data array, data D1 of a physical block in the physical page P0 is stored in entries of the corresponding cache lines. Thus, data of the same physical block of the same physical page is stored in two cache lines.
Under this condition, if one process writes data D2 to the main memory using the virtual address VA, then the tag information indicating the physical page P0 and the data D2, respectively, are stored in the entries, in the tag array and data array, of the cache line corresponding to the virtual index VI, as shown in (b) of FIG. 12. The data D2 is also written to the main memory. However, within the data array, in the cache line corresponding to the virtual index VI′, the old data D1 is still stored.
Thus, although data of the same physical block of the same physical page is stored in the cache lines corresponding to the virtual indexes VI and VI′, respectively, data in the cache lines corresponding to the virtual indexes VI and VI′ is different from each other, which results in a cache aliasing issue.
The following technology is one example of how to solve this cache aliasing issue.
Address translation is performed on a virtual tag of a virtual address of a cache line to be accessed, and thereby a physical tag is obtained. This physical tag is compared not only with the tag information of the accessed cache line but also with the tag information of cache lines that potentially have a cache aliasing issue with the accessed cache line. Then, when the physical tag agrees with the tag information of the accessed cache line and also agrees with the tag information of the cache lines potentially having the cache-aliasing relationship, cache aliasing is detected and the entire cache memory is flushed (e.g. Japanese Laid-Open Patent Application Publication No. H6-139146).
According to this technology, however, the process of detecting cache aliasing cannot be commenced until the address translation from a virtual address to a physical address is completed, which leads to a decrease in the memory access rate. In addition, flushing the entire cache memory when cache aliasing is detected results in an increase in the number of times to access the main memory, whereby increasing the average amount of time required for the memory access.